package main.面试金典第六版;

import java.util.*;

public class Interview02 {
    public static void main(String[] args) {
        System.out.println("面试题02.01：移除重复节点");
        System.out.println("面试题02.02：返回倒数第 k 个节点");
        System.out.println("面试题02.03：删除中间节点");
        System.out.println("面试题02.04：分割链表");
        System.out.println("面试题02.05：链表求和");
        System.out.println("面试题02.06：回文链表");
        System.out.println("面试题02.07：链表相交");
        System.out.println("面试题02.08：环路检测");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Interview_02_01{
    public ListNode removeDuplicateNodes(ListNode head) {
        ListNode vir=new ListNode(0);
        vir.next=head;
        Set<Integer> set=new HashSet<>();
        while (vir.next!=null) {
            if (set.isEmpty()||!set.contains(vir.next.val)) {
                set.add(vir.next.val);
                vir=vir.next;
            }else {
                vir.next=vir.next.next;
            }
        }
        return head;
    }
}

class Interview_02_02{
    public int kthToLast(ListNode head, int k) {
        int length=0;
        ListNode vir=head,temp=head;
        while (temp!=null) {//计数
            length++;
            temp=temp.next;
        }
        temp=vir;
        for (int i=0;i<k;i++) temp=temp.next;//先行
        while (temp!=null) {
            vir=vir.next;
            temp=temp.next;
        }
        return vir.val;
    }
}

class Interview_02_03{
    public void deleteNode(ListNode node) {
        node.val=node.next.val;
        node.next=node.next.next;
    }
}

class Interview_02_04{
    public ListNode partition(ListNode head, int x) {
        List<Integer> list=new ArrayList<>();
        ListNode temp=head;
        while (temp!=null) {
            list.add(temp.val);
            temp=temp.next;
        }
        Collections.sort(list);
        temp=head;
        for (int i=0;i<list.size();i++){
            temp.val=list.get(i);
            temp=temp.next;
        }
        return head;
    }
}

class Interview_02_05{
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) head = tail = new ListNode(sum % 10);
            else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) tail.next = new ListNode(carry);
        return head;
    }
}

class Interview_02_06{
    public boolean isPalindrome(ListNode head) {
        List<Integer> list=new ArrayList<>();
        while (head!=null) {
            list.add(head.val);
            head=head.next;
        }
        int left=0,right=list.size()-1;
        while (left<right) {
            if (!list.get(left).equals(list.get(right))) return false;
            left++;
            right--;
        }
        return true;
    }
}

class Interview_02_07{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA=headA,tempB=headB;
        while (tempA!=null&&tempB!=null) {
            tempA=tempA.next;
            tempB=tempB.next;
        }
        if (tempA==null) {
            tempA=headB;
            while (tempB!=null) {
                tempA=tempA.next;
                tempB=tempB.next;
            }
            tempB=headA;
        }else {
            tempB=headA;
            while (tempA!=null) {
                tempA=tempA.next;
                tempB=tempB.next;
            }
            tempA=headB;
        }
        while (tempA!=tempB) {
            tempA=tempA.next;
            tempB=tempB.next;
        }
        return tempA;
    }
}

class Interview_02_08{
    public ListNode detectCycle(ListNode head) {
        if (head==null||head.next==null) return null;
        ListNode slow=head,fast=head;
        do {
            if (fast!=null&&fast.next!=null) {
                fast = fast.next.next;
                slow = slow.next;
            }else return null;
        }while (fast!=slow);//判断存在环
        if (fast!=null) {//填补快慢指针步差
            slow = head;
            while (slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
        }
        return fast;
    }
}